package 二分查找;

/**
 * @author xiaok
 * @create 2020--09-08 14:23
 */

public class 大于给定元素的最小元素_744 {
    /*
    Input:
    letters = ["c", "f", "j"]
    target = "d"
    Output: "f"

    Input:
    letters = ["c", "f", "j"]
    target = "k"
    Output: "c"
    Copy to clipboardErrorCopied
    题目描述：给定一个有序的字符数组 letters 和一个字符 target，要求找出 letters 中大于 target 的最小字符，如果找不到就返回第 1 个字符。
     */
    public char nextGreatestLetter(char[] letters, char target) {
        int n = letters.length;
        int l = 0, h = n - 1;
        while (l <= h) {
            int m = l + (h - l) / 2;
            if (letters[m] <= target) {
                l = m + 1;
            } else {
                h = m - 1;
            }
        }
        // 说明找不到
        return l < n ? letters[l] : letters[0];
    }

    public char nextGreatestLetter2(char[] letters, char target) {
        int n = letters.length;
        int low =0;
        int high = letters.length-1;
        int middle =0;
        while( low <= high ){ //找到最接近target的数
            middle = low + (high-low)/2;
            if(letters[middle] > target){
                high = middle-1;
            }else{
                low = middle+1;
            }
        }
        return  high < n?letters[high]:letters[0];

    }

}
